package algorithms.leaning.class09;

import java.util.HashMap;
import java.util.Map;

/**
 * 一种特殊的单链表节点类描述如下
 * class Node {
 * int value;
 * Node next;
 * Node rand;
 * Node(int val) {
 * value = val;
 * }
 * }
 * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
 * 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
 * 【要求】
 * 时间复杂度O(N)，额外空间复杂度O(1)
 *
 * @author guichang
 * @date 2021/6/6
 */

@SuppressWarnings("all")
public class Code5_链表_复制随机指针 {

    public static void main(String[] args) {

    }

    private static class Node {
        int value;
        Node next;
        Node rand;

        Node(int val) {
            value = val;
        }
    }

    /**
     * TODO
     * 不使用额外空间复杂度
     * 时间复杂度 O(N)
     * 空间复杂度 O(1)
     */
    public static Node CopyWithoutMap(Node head) {
        return null;
    }

    /**
     * 使用容器的方式解决
     * 时间复杂度 O(N)
     * 空间复杂度 O(N)
     *
     * @param head
     * @return
     */
    public static Node CopyWithMap(Node head) {
        if (head == null) {
            return head;
        }
        Map<Node, Node> map = new HashMap<>();
        Node curr = head;
        // 一对一创建并关联新节点
        while (curr != null) {
            map.put(curr, new Node(curr.value));
            curr = curr.next;
        }
        // 设置next和rand指针
        curr = head;
        while (curr != null) {
            Node newNode = map.get(curr);
            newNode.next = curr.next;
            newNode.rand = curr.rand;
            curr = curr.next;
        }
        // 返回head对应的新头节点即可
        return map.get(head);
    }

}